package com.le.enhance.class6;

import org.junit.Test;

/**
 * 字符串匹配问题
 * 给定字符串str,在给定匹配字符串rex, . 可以匹配任意字符, *: 代表前边的字符可以使0个或多个
 */
public class Code_03_RegularExpressionMatch {

    public static boolean getMatch(String str, String rex) {
        return process(str.toCharArray(), rex.toCharArray(), 0, 0);
    }

    /**
     * @param str 源字符串
     * @param rex 匹配字符串
     * @param i   str索引
     * @param j   rex索引
     * @return true, false
     */
    public static boolean process(char[] str, char[] rex, int i, int j) {
        // 1. j 到了最后一个元素,判断i是否匹配完
        if (j == rex.length) {
            return i == str.length;
        }
        // 2. j+1->数组边界或者不等于 *
        if (j + 1 == rex.length || rex[j + 1] != '*') {
            return i != str.length
                    && (str[i] == rex[j] || rex[j] == '.')
                    && process(str, rex, i + 1, j + 1);
        }
        // 3. j+1-->等于 *, j 位置元素可以有0个或多个, 且当前元素可以匹配
        while (i != str.length && (str[i] == rex[j] || rex[j] == '.')) {
            if (process(str, rex, i, j + 2)) {
                return true;
            }
            i++;
        }
        // 4. j+1-->等于 *, j 位置元素可以有0个或多个, 当前元素不匹配
        return process(str, rex, i, j + 2);
    }

    @Test
    public void test() {
        String str = "abc";
//        String rex = "abc";
        String rex = "a.c";
//        System.out.println(getMatch(str,rex));

        String s = "abcccdefg";
        String r = "ab.*d.*e.*";
        System.out.println(getMatch(s, r));
    }
}
